package datastruct.algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class QuickSorter {

    public static void main(String[] args) {

        int[] nums = {3,4,7,4,9,12,56,12,34,89};
        QuickSorter qs = new QuickSorter();
        System.out.println(qs.findMid(nums));
//        qs.sort(nums);
        System.out.println(qs.findMidAfterSort(nums));
    }

    /**
     * 查找中位数
     */
    public double findMid(int[] nums){
        int n = nums.length;
        if((n&1)==1) return findKMin(nums,n/2);
        //TODO: 2021/8/4 这样还不如直接排序取出中间两个
        int a = findKMin(nums,n/2+1);
        int b = findKMin(nums,n/2);
        return (a+b)*1.0/2;
    }

    /**
     * 排序后查找中位数
     */
    public double findMidAfterSort(int[] nums){
        int n = nums.length;
        //为了不改变原数组，复制一份
        int[] copy = new int[n];
        System.arraycopy(nums,0,copy,0,n);
        sort(copy);
        if((n&1)==1) return copy[n/2];
        return (copy[n/2]+copy[n/2-1])*1.0/2;
    }

    /**
     * 查找第k小的数
     */
    public int findKMin(int[] nums, int k){
        int n = nums.length;
        //为了不改变原数组，复制一份
        int[] copy = new int[n];
        System.arraycopy(nums,0,copy,0,n);
        k = k - 1; //下标从0开始
        int l = 0, r = n - 1;
        int cur = partation(copy,l,r);
        while (cur!=k){
            if(cur>k){
                r = cur - 1;
                cur = partation(copy,l,r);
            }else if(cur<k){
                l = cur + 1;
                cur = partation(copy,l,r);
            }
        }
        return copy[k];
    }

    /**
     * 快排
     * @param nums
     */
    public void sort(int[] nums){
        quickSort(nums,0,nums.length-1);
    }

    public static void quickSort(int[] nums, int l, int r){
        if(l>=r) return;
        int mid = partation(nums,l,r);
        quickSort(nums,l,mid-1);
        quickSort(nums,mid+1,r);
    }

    //划分，返回枢轴量最后的位置
    public static int partation(int[] nums, int l, int r){
        int pivot = nums[l];
        int i = l, j = r;
        while (i<j){
            //从右边寻找小于pivot的
            while (i<j&&nums[j]>=pivot) j--;
            nums[i] = nums[j];
            //从左边找大于pivot的
            while (i<j&&nums[i]<=pivot) i++;
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        return i;
    }
}
